import java.util.ArrayList;
import java.util.Stack;
import java.util.stream.IntStream;

/**
 * Author: Evgeniy Krasko.
 * Date: 4/7/14
 */

public class Embedder {

    private Embedder() {
    }

    public static ArrayList<ArrayList<Integer>> getEmbedding(int vCount, int[] from, int[] to) {
        if (from.length > 3 * vCount - 6) return new ArrayList<>();

        ArrayList<Edge> edges = new ArrayList<>();
        ArrayList<Vertex> vertices = new ArrayList<>();
        Stack<ConflictPair> s = new Stack<>();
        ArrayList<Vertex> roots = new ArrayList<>();

        IntStream.range(0, vCount).forEach(i -> vertices.add(new Vertex()));
        IntStream.range(0, vCount).forEach(i -> vertices.get(i).index = i);

        for (int i = 0; i < from.length; ++i) {
            Edge e = new Edge(vertices.get(from[i]), vertices.get(to[i]));
            e.start.incident.add(e);
            e.end.incident.add(e);
            edges.add(e);
        }

        for (Vertex v : vertices) {
            if (v.height == Integer.MAX_VALUE) {
                v.height = 0;
                roots.add(v);
                processEdges(v);
            }
        }

        sortIncidenceLists(edges, vertices);
        for (Vertex r : roots) {
            if (!testForLRPartition(r, s)) return new ArrayList<>();
        }

        edges.forEach(e -> e.nestingDepth = e.nestingDepth * sign(e));

        sortIncidenceLists(edges, vertices);

        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        IntStream.range(0, vCount).forEach(i -> graph.add(new ArrayList<>()));

        roots.forEach(r -> embed(r, graph));

        return graph;
    }

    private static void embed(Vertex v, ArrayList<ArrayList<Integer>> graph) {
        for (Edge ei : v.incident) {
            if (ei.start != v) continue;
            Vertex w = ei.end;
            ei.ref = w.ref;
            w.ref = ei;
            if (ei == w.parentEdge) {
                graph.get(w.index).add(v.index);
                v.ref = null;
                embed(w, graph);
                for (Edge e = v.ref; e != null; e = e.ref) {
                    if (e.side == -1) {
                        graph.get(v.index).add(e.start.index);
                    }
                }
                graph.get(v.index).add(w.index);
                for (Edge e = v.ref; e != null && e.side != -1; e = e.ref) {
                    graph.get(v.index).add(e.start.index);
                }
            } else {
                graph.get(v.index).add(w.index);
            }
        }
    }

    private static int sign(Edge e) {
        if (e.ref != null) {
            e.side = e.side * sign(e.ref);
            e.ref = null;
        }
        return e.side;
    }

    private static boolean conflicting(Interval i, Edge e) {
        return (!i.isEmpty()) && (i.top.low > e.low);
    }

    private static int lowest(ConflictPair p) {
        if (p.left.isEmpty()) return p.right.bottom.low;
        if (p.right.isEmpty()) return p.left.bottom.low;
        return Math.min(p.left.bottom.low, p.right.bottom.low);
    }

    private static boolean testForLRPartition(Vertex v, Stack<ConflictPair> s) {
        Edge e = v.parentEdge;
        boolean first = true;
        for (Edge ei : v.incident) {
            if (ei.start != v) continue;
            ConflictPair stackTop = s.isEmpty() ? null : s.peek();
            if (ei == ei.end.parentEdge) {
                if (!testForLRPartition(ei.end, s)) return false;
            } else {
                ei.lowEdge = ei;
                s.push(new ConflictPair(new Interval(), new Interval(ei, ei)));
            }
            if (ei.low < v.height) {
                if (first) {
                    e.lowEdge = ei.lowEdge;
                } else {
                    ConflictPair p = new ConflictPair(new Interval(), new Interval());
                    do {
                        ConflictPair q = s.pop();
                        if (!q.left.isEmpty()) q.swap();
                        if (!q.left.isEmpty()) {
                            return false;
                        }
                        if (q.right.bottom.low > e.low) {
                            if (p.right.isEmpty()) {
                                p.right.top = q.right.top;
                            } else {
                                p.right.bottom.ref = q.right.top;
                            }
                            p.right.bottom = q.right.bottom;
                        } else {
                            q.right.bottom.ref = e.lowEdge;
                        }
                    } while (s.peek() != stackTop);
                    while (conflicting(s.peek().left, ei) || conflicting(s.peek().right, ei)) {
                        ConflictPair q = s.pop();
                        if (conflicting(q.right, ei)) q.swap();
                        if (conflicting(q.right, ei)) {
                            return false;
                        }
                        p.right.bottom.ref = q.right.top;
                        if (q.right.bottom != null) {
                            p.right.bottom = q.right.bottom;
                        }
                        if (p.left.isEmpty()) {
                            p.left.top = q.left.top;
                        } else {
                            p.left.bottom.ref = q.left.top;
                        }
                        p.left.bottom = q.left.bottom;
                    }
                    if (!p.left.isEmpty() || !p.right.isEmpty()) {
                        s.push(p);
                    }
                }
            }
            first = false;
        }
        if (e != null) {
            Vertex u = e.start;
            while (!s.isEmpty() && lowest(s.peek()) == u.height) {
                ConflictPair p = s.pop();
                if (p.left.bottom != null) {
                    p.left.bottom.side = -1;
                }
            }
            if (!s.isEmpty()) {
                ConflictPair p = s.pop();

                while (p.left.top != null && p.left.top.end == u) {
                    p.left.top = p.left.top.ref;
                }
                if (p.left.top == null && p.left.bottom != null) {
                    p.left.bottom.ref = p.right.bottom;
                    p.left.bottom.side = -1;
                    p.left.bottom = null;
                }

                while (p.right.top != null && p.right.top.end == u) {
                    p.right.top = p.right.top.ref;
                }
                if (p.right.top == null && p.right.bottom != null) {
                    p.right.bottom.ref = p.left.bottom;
                    p.right.bottom.side = -1;
                    p.right.bottom = null;
                }

                s.push(p);
            }
            if (e.low < u.height) {
                Edge hl = s.peek().left.top;
                Edge hr = s.peek().right.top;
                if (hl != null && (hr == null || hl.low > hr.low)) {
                    e.ref = hl;
                } else {
                    e.ref = hr;
                }
            }
        }
        return true;
    }

    private static void processEdges(Vertex v) {
        Edge e = v.parentEdge;
        for (Edge vw : v.incident) {
            if (!vw.oriented) {
                vw.oriented = true;
                if (vw.start != v) {
                    vw.flip();
                }
                Vertex w = vw.end;
                vw.low = vw.low2 = v.height;
                if (w.height == Integer.MAX_VALUE) {
                    w.parentEdge = vw;
                    w.height = v.height + 1;
                    processEdges(w);
                } else {
                    vw.low = w.height;
                }
                vw.nestingDepth = 2 * vw.low;
                if (vw.low2 < v.height) {
                    ++vw.nestingDepth;
                }
                if (e != null) {
                    if (vw.low < e.low) {
                        e.low2 = Math.min(e.low, vw.low2);
                        e.low = vw.low;
                    } else if (vw.low > e.low) {
                        e.low2 = Math.min(e.low2, vw.low);
                    } else {
                        e.low2 = Math.min(e.low2, vw.low2);
                    }
                }
            }
        }

    }

    private static void sortIncidenceLists(ArrayList<Edge> edges, ArrayList<Vertex> vertices) {
        int size = 4 * vertices.size() + 1;

        ArrayList<ArrayList<Edge>> buckets = new ArrayList<>();
        IntStream.range(0, size).forEach(i -> buckets.add(new ArrayList<>()));

        edges.forEach(e -> buckets.get(e.nestingDepth + size / 2).add(e));
        vertices.forEach(v -> v.incident.clear());

        buckets.forEach(bucket -> bucket.forEach(e -> {
            e.start.incident.add(e);
            e.end.incident.add(e);
        }));
    }

    private static class Edge {
        int side = 1, low = -1, low2 = -1, nestingDepth = -1;
        Edge lowEdge = null, ref = null;
        Vertex start = null, end = null;
        boolean oriented = false;

        Edge(Vertex start, Vertex end) {
            this.start = start;
            this.end = end;
        }

        public void flip() {
            Vertex t = start;
            start = end;
            end = t;
        }
    }

    private static class Vertex {
        int height = Integer.MAX_VALUE, index = -1;
        Edge parentEdge = null, ref = null;
        ArrayList<Edge> incident = new ArrayList<>();
    }

    private static class ConflictPair {
        Interval left, right;

        ConflictPair(Interval left, Interval right) {
            this.left = left;
            this.right = right;
        }

        public void swap() {
            Interval t = left;
            left = right;
            right = t;
        }
    }

    private static class Interval {
        Edge top, bottom;

        Interval() {
            this(null, null);
        }

        Interval(Edge top, Edge bottom) {
            this.top = top;
            this.bottom = bottom;
        }

        boolean isEmpty() {
            return top == null && bottom == null;
        }
    }
}
